package com.gxc.linkedList;

/**
 * 25. K 个一组翻转链表
 * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
 *
 * k 是一个正整数，它的值小于或等于链表的长度。
 * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 *
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 */
public class ReverseKGroup {

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        ListNode head2 = new ListNode(2);
        ListNode head3 = new ListNode(3);
        ListNode head4 = new ListNode(4);
        ListNode head5 = new ListNode(5);
        head1.next = head2;
        head2.next = head3;
        head3.next = head4;
        head4.next = head5;

        ListNode res = reverseKGroup(head1, 2);
        System.out.println(res);
    }

    public static ListNode handle(ListNode head, int k) {
        if (k<2) return head;
        int l = 0;
        ListNode node = head;
        ListNode tail = new ListNode(-1);
        tail.next = head;
        while (node!=null) {
            node = node.next;
            l++;
        }

        ListNode pre = tail;
        ListNode last = null;
        ListNode node1 = head;
        ListNode node2 = head.next;
        ListNode next = null;
        int count = 0;
        while (l>=k) {
            //翻转链表  需要三个 next  node1  node2
            while (count<k-1) {
                next = node2.next;
                node2.next = node1;
                if (count == 0) {
                    last = node1;
                }
                node1 = node2;
                node2 = next;
                count++;
            }
            pre.next = node1;
            last.next = node2;
            pre = last;
            node1 = node2;
            if (node1!=null) node2 = node1.next;
            l = l-k;
            count = 0;
        }
        return tail.next;
    }

      public static class ListNode {
          int val;
          ListNode next;
          ListNode() {}
          ListNode(int val) { this.val = val; }
          ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      }

        public ListNode reverseKGroup2(ListNode head, int k) {
            ListNode hair = new ListNode(0);
            hair.next = head;
            ListNode pre = hair;

            while (head != null) {
                ListNode tail = pre;
                // 查看剩余部分长度是否大于等于 k
                for (int i = 0; i < k; ++i) {
                    tail = tail.next;
                    if (tail == null) {
                        return hair.next;
                    }
                }
                ListNode nex = tail.next;
                ListNode[] reverse = myReverse(head, tail);
                head = reverse[0];
                tail = reverse[1];
                // 把子链表重新接回原链表
                pre.next = head;
                tail.next = nex;
                pre = tail;
                head = tail.next;
            }

            return hair.next;
        }

        //翻转
        public ListNode[] myReverse(ListNode head, ListNode tail) {
            ListNode prev = tail.next;
            ListNode p = head;
            while (prev != tail) {
                ListNode nex = p.next;
                p.next = prev;
                prev = p;
                p = nex;
            }
            return new ListNode[]{tail, head};
        }

    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode hair = new ListNode(0);
        hair.next = head;
        ListNode prev = hair;

        while (head != null) {
            ListNode tail = prev;
            //判断剩余链表长度是否满足k
            for (int i = 0; i < k; i++) {
                tail = tail.next;
                if (tail == null) {
                    return hair.next;
                }
            }

            ListNode next = tail.next;
            ListNode[] reserve = myReserve(head, tail);

            ListNode h = reserve[0];
            ListNode t = reserve[1];
            // 把子链表重新接回原链表
            t.next = next;
            prev.next = h;

            prev = t;
            head = next;
        }

        return hair.next;
    }

    private static ListNode[] myReserve(ListNode head, ListNode tail) {
        ListNode prev = null;
        ListNode cur = head;
        while (tail != prev) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return new ListNode[]{tail, head};
    }

    public ListNode reverseKGroup3(ListNode head, int k) {
        ListNode dummy = new ListNode(0), prev = dummy, curr = head, next;
        dummy.next = head;
        int length = 0;
        while(head != null) {
            length++;
            head = head.next;
        }
        head = dummy.next;
        for(int i = 0; i < length / k; i++) {
            for(int j = 0; j < k - 1; j++) {
                next = curr.next;
                curr.next = next.next;
                next.next = prev.next;
                prev.next = next;
            }
            prev = curr;
            curr = prev.next;
        }
        return dummy.next;
    }

}
